The present invention relates to a method for random-access communication with binary feedback. Specifically, the present invention relates to a method for random-access communication with binary feedback in communication networks with time-slotted transmission channels which are accessed by a plurality of terminals, whereby random-access means that users attempt to communicate whenever they have information to transmit, whereby communication networks with time-slotted communication channels are communication networks where data may be transmitted only at regular prescribed time intervals, so called time-slots, and whereby binary feedback means that users of the communication network are provided with information about whether or not a previous time-slot contained a successfully transmitted data packet.
In communications, random-access to a single channel, as for instance a satellite communication network, a local area network, or a mobile radio network, requires organization and coordination of a plurality of users efficiently sharing the resources of said single channel, said channel being a collision-type, packet switched, time-slotted transmission channel.
Access algorithms for this general model have been proposed and analyzed in the paper xe2x80x9cCollision Resolution Algorithms and Random-Access Communications,xe2x80x9d published by Springer in 1981, in Multi-User Communications, CISM Courses and Lectures, number 265 (document D1). In document D1, a collision resolution algorithm for randomly accessing a collision-type channel with feedback is defined as a protocol for the transmission and re-transmission of packets by individual transmitters, all packets involved in the collision eventually being re-transmitted successfully and all transmitters (not only those whose packets collided) eventually and simultaneously becoming aware that these packets have been successfully re-transmitted. The collision is considered to be resolved precisely at the point where all the transmitters simultaneously become aware that the colliding packets have all been successfully re-transmitted. An interval is considered to be resolved when all the messages generated in that interval have been successfully transmitted. A basic interval commences after a prior interval has fbeen resolved. These definitions given in document D1 will be used throughout the remainder of this text.
Access algorithms for the general model described above have also been proposed and analyzed in the paper xe2x80x9cRandom Multiple-Access Communication and Group Testing,xe2x80x9d published in April 1984, in IEEE Transactions on Communications, volume COM-32, pages 769-784 (document D2); and in the paper xe2x80x9cRandom-Access Communication with Multiple Reception,xe2x80x9d in May 1990, in IEEE Transactions on Information Theory, volume IT-36, pages 614-622 (document D3). In both of these papers, document D2 and D3, models of binary success/no-success feedback have been studied. Success/no-success feedback provides the users of the transmission channel with information indicating as to whether or not a given slot contained a successfully transmitted packet. This is required, for instance, in situations where a receiver cannot distinguish between channel noise and collision noise, and could be achieved, for example, by means of a Cyclic Redundancy Check (CRC). As is pointed out in document D3, spread-spectrum random-access systems can result in success/no-success feedback when the users keep the transmitted power spectrum low. This makes it difficult to distinguish the noise-like waveform, resulting from the collision of two or more transmitted packets, from noise alone. Another example of binary feedback might be in the area of wireless Asynchronous Transfer Mode (ATM) networks where the low-rate feedback of the access point of the mobile user informs the user as to whether or not an error in the transmitted packet (which forces a re-transmission) has been detected. The best performance, measured in terms of successful transmissions per channel use, previously reported for success/no-success feedback is a throughput of 0.329 (32.9%), as stated in document D3.
In the paper xe2x80x9cRandom Multiple Access in a Channel with Binary Success/No-Success Feedback,xe2x80x9d published in 1990, in Problemy Peredachi Informatsii, volume 26, number 3, pages 67-82 (document D5), it was stated that the throughput of success/no-success feedback might be improved to 1/e (xcx9c0.368), i.e. to the maximum achievable throughput of ALOHA, described in xe2x80x9cALOHA Packet System With and Without Slot and Capture,xe2x80x9d published in 1972 and reprinted in 1975, in Computer Communication Review, volume 5, pages 28-42 (document D4).
The notion of an auxiliary user in the context of random accessing systems was introduced in document D2 , and adopted in document D5 and in the paper xe2x80x9cA Limited Sensing Random-Access Algorithm with Binary Success Failure Feedback,xe2x80x9d in 1989, in IEEE Transactions on Communications, volume COM-37, pages 526-530 (document D6). The auxiliary user is a dummy user who transmits a dummy packet during particular slots. The purpose of the auxiliary user""s action is to implicitly transform the success/no-success feedback into a ternary idle/success/collision-type feedback by sacrificing one slot. As already mentioned, for a protocol to be a collision resolution algorithm, it is mandatory that all the users recognize the end of a collision resolution. Without an auxiliary user or a similar concept of test packets, as was described in document D5, this would not be possible for pure success/no-success feedback in an environment with a plurality of users. In the algorithm described in document D6, a dummy packet is transmitted by an auxiliary user after every occurrence of a no-success feedback, i.e. a negative feedback, each time sacrificing one slot. Also in the algorithm described in document D5, possibly multiple slots are sacrificed for dummy packets transmitted by an auxiliary user during the resolution of a collision.
It is an object of this invention to propose a new and improved method for random-access communication with binary feedback in communication networks with time-slotted transmission channels which are accessed by a plurality of terminal devices (users), whereby unsuccessfully transmitted packets are retransmitted, and whereby an auxiliary user transmits dummy packets.
According to the present invention, these objects are achieved particularly through the features of the characterizing part of the independent claims. In addition, further advantageous embodiments follow from the dependent claims and the description.
In particular, these objects are achieved according to the invention in that the order of re-transmitting unsuccessfully transmitted packets, i.e. packets that were involved in a collision, depends on their respective position in an interval, whereby this position is determined by the numeric value of a parameter assigned to each packet, and whereby these numeric values are altered after a negative feedback (no-success feedback) occurred during the time when the collision of packets is being resolved. Thus, rather than sacrificing a time slot by transmitting a dummy packet to determine whether the negative feedback (no-success feedback) was due to a collision of re-transmitted packets in the respective slot or whether it was due to this slot having been empty, numeric values of parameters determining the order of the re-transmission of these packets are altered and the resolution of the collision is continued. This has the advantage that, without sacrificing a time slot for a dummy packet, repeated collisions can be resolved without risking a deadlock due to successive re-transmission of the same colliding packets.
In a preferred embodiment of the present invention, the numeric value of said parameter assigned to each packet is based on the generation time of the respective packet.
In the present invention, said step of altering the numeric values of said parameters is preferably done by randomization.
Preferably, in the present invention, a dummy packet, to determine whether a negative feedback (no-success feedback) was due to a collision of packets in the respective slot or whether it was due to this slot having been empty, is only transmitted following certain occurrences of negative feedback, namely following the first negative feedback after a prior collision has been (fully) resolved. This has the advantage that the number of slots sacrificed for dummy packets can thereby be reduced.
Preferably, enabling the re-transmission of said unsuccessfully transmitted packets is determined in the present invention by a predefined parameter dividing said interval into two portions. This approach provides an easy means to distinctively enable subsets of the interval containing the colliding packets.
In a variant of the present invention, said predefined parameter is varied depending on the number of collisions. This has the advantage that the method and its efficiency can be adapted dynamically to the current situation of the transmission channel.
Preferably, in the present invention, a collision is resolved after two consecutive successful transmissions indicated by two consecutive positive feedback messages (success feedback).
In the present invention, terminal devices not involved in a collision resolution are preferably only allowed to transmit packets after they have learned that the collision is resolved.
In a preferred embodiment of the present invention, at least certain of said communication networks are mobile radio networks and at least certain of said terminal devices are mobile telephones.